//
//  Common.h
//  ThreadCache
//
//  Created by 卜绎皓 on 2023/1/31.
//
#pragma once

#include <iostream>
#include <vector>
#include <assert.h>
#include <thread>
#include <time.h>
#include <algorithm>
#include <mutex>
#include <unordered_map>


using std::cout;
using std::endl;

#ifdef _WIN32
    #include <windows.h>
#else
    // ...
#endif


//小于等于MAX_BYTES，就找thread cache申请
//大于MAX_BYTES，就直接找page cache或者系统堆申请
static const size_t MAX_BYTES = 256 * 1024;
//thread cache和central cache自由链表哈希桶的表大小
static const size_t NFREELISTS = 208;
//page cache中哈希桶的个数
static const size_t NPAGES = 129;
//页大小转换偏移，即一页定义为2^13，也就是8KB
static const size_t PAGE_SHIFT = 13;


#ifdef _WIN64
    typedef unsigned long long PAGE_ID;
#elif _WIN32
    typedef size_t PAGE_ID;
#else
    //linux
    typedef size_t PAGE_ID;
#endif

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // linuxœ¬brk mmapµ»
#endif

    
    if (ptr == nullptr)
        throw std::bad_alloc();

    return ptr;
}


inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    // sbrk unmmapµ»
#endif
}



static void*& NextObj(void* obj)
{
    return *(void**)obj;
}

class FreeList
{
public:
    
    //将释放的头对象头插进自由链表
    void Push(void* obj)
    {
        assert(obj);
        //头插
        NextObj(obj) = _freeList;
        _freeList = obj;
        
        ++_size;
    }
    
    //插入一段范围的对象到自由链表
    void PushRange(void* start, void* end,size_t n)
    {
        assert(start);
        assert(end);

        //头插
        NextObj(end) = _freeList;
        _freeList = start;
        
        _size += n;
    }
    
    
    //从自由链表头部获取对象
    void* Pop()
    {
        assert(_freeList);
        
        //头删
        void* obj = _freeList;
        _freeList = NextObj(_freeList);
        
        return obj;
    }
    
    //从自由链表获取一段范围的对象
    void PopRange(void*& start,void*& end,size_t n)
    {
        assert(n <= _size);
        
        //头删
        start = _freeList;
        end = start;
        
        for(size_t i = 0; i < n - 1;i++)
        {
            end = NextObj(end);
        }
        
        _freeList = NextObj(end);//自由链表指向end的下一个对象
        NextObj(end) = nullptr;//取出的一段链表的表尾置空
        
        _size -= n;
    }
    
    bool Empty()
    {
        return _freeList == nullptr;
    }
                             
    size_t& MaxSize()
    {
        return _maxSize;
    }
    
    size_t Size()
    {
        return _size;
    }
private:
    void* _freeList = nullptr;//自由链表
    size_t _maxSize = 1;
    size_t _size = 0;
};



//管理对齐和映射等关系
class SizeClass
{
public:
    
    static inline size_t _RoundUp(size_t bytes,size_t alignNum)
    {
//        //一般写法
//        size_t alignSize = 0;
//        if(bytes % alignNum != 0)
//        {
//            alignSize = (bytes / alignNum + 1)*alignNum;
//        }
//        else
//        {
//            alignSize = bytes;
//        }
//        return alignSize;
        
        //位运算写法
        return ((bytes + alignNum - 1)&~(alignNum-1));
    }
    
    //获取向上对齐后的字节数
    static inline size_t RoundUp(size_t bytes)
    {
        if(bytes <= 128)
        {
            return _RoundUp(bytes, 8);
        }
        
        else if(bytes <= 1024)
        {
            return _RoundUp(bytes, 16);
        }
        
        else if(bytes <= 8*1024)
        {
            return _RoundUp(bytes, 128);
        }
        
        else if(bytes <= 64*1024)
        {
            return _RoundUp(bytes, 1024);
        }
        
        else if(bytes <= 256*1024)
        {
            return _RoundUp(bytes, 8*1024);
        }
        
        else
        {
            //大于256KB的按页对齐
            return _RoundUp(bytes, 1 << PAGE_SHIFT);
        }
    }
    
    
    
    //获取对应哈希桶的下标
    static inline size_t _Index(size_t bytes,size_t alignNum)
    {
//        //一般写法
//        size_t index = 0;
//        if(bytes % alignNum != 0)
//        {
//            index = bytes / alignNum;
//        }
//        else
//        {
//            index = bytes / alignNum - 1;
//        }
//        return index;
        
        
        
        //位运算写法
        return ((bytes + (1 << alignNum) - 1) >> alignNum) - 1;
    }
    
    //获取对应哈希桶的下标
    static inline size_t Index(size_t bytes)
    {
        assert(bytes <= MAX_BYTES);
        
        //每个区间有多少个自由链表
        static size_t grounpArray[4] = {16,56,56,56};
        
        if(bytes <= 128)
        {
            return _Index(bytes, 3);
        }
        
        else if(bytes <= 1024)
        {
            return _Index(bytes - 128, 4) + grounpArray[0];
        }
        
        else if(bytes <= 8*1024)
        {
            return _Index(bytes - 128, 7) + grounpArray[0] + grounpArray[1];
        }
        
        else if(bytes <= 64*1024)
        {
            return _Index(bytes - 128, 10) + grounpArray[0] + grounpArray[1] + grounpArray[2];
        }
        
        else if(bytes <= 256*1024)
        {
            return _Index(bytes - 128, 13) + grounpArray[0] + grounpArray[1] + grounpArray[2] + grounpArray[3];
        }
        
        else
        {
            assert(false);
            return  -1;
        }
    }
    
    //管理对齐和映射关系
    //thread cache一次从central cache获取对象的上限
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);
        
        //对象越小，计算出的上限越高
        //对象越大，计算出的上限越低
        int num = MAX_BYTES / size;
        if(num < 2)
            num = 2;
        if(num > 512)
            num = 512;
        
        return num;
    }
    
    //central cache一次向page cache获取多少页
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size); //计算出thread cache一次向central cache申请对象的个数上限
        size_t nPage = num*size; //num个size大小的对象所需的字节数

        nPage >>= PAGE_SHIFT; //将字节数转换为页数
        if (nPage == 0) //至少给一页
            nPage = 1;

        return nPage;
    }
    
};

//管理以页为单位的大块内存
struct Span
{
    PAGE_ID _pageId = 0;        //大块内存起始页的页号
    size_t _n = 0;              //页的数量

    Span* _next = nullptr;      //双链表结构
    Span* _prev = nullptr;

    size_t _useCount = 0;       //切好的小块内存，被分配给thread cache的计数
    void* _freeList = nullptr;  //切好的小块内存的自由链表
    
    size_t _objSize = 0;        //切好的小对象的大小
    
    bool _isUes = false;        //是否在被使用
};


//带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }
    
    Span* Begin()
    {
        return _head->_next;
    }
    
    Span* End()
    {
        return _head;
    }
    
    
    bool Empty()
    {
        return _head->_next == _head;
    }
    
    void PushFront(Span* span)
    {
        Insert(Begin(), span);
    }
    
    Span* PopFront()
    {
        Span* front = _head->_next;
        Erase(front);
        return front;
    }
    
    
    void Insert(Span* pos,Span* newSpan)
    {
        assert(pos);
        assert(newSpan);
        
        Span* prev = pos->_prev;
        
        prev->_next = newSpan;
        newSpan->_prev = prev;
        newSpan->_next = pos;
        pos->_prev = newSpan;
    }
    
    void Erase(Span* pos)
    {
        assert(pos);
        assert(pos != _head);
        
        Span* prev = pos->_prev;
        Span* next = pos->_next;
        
        prev->_next = next;
        next->_prev = prev;
    }
private:
    Span* _head;
public:
    std::mutex _mtx;//桶锁
};
